11653번 소인수분해

Day9 9단계 20231026

• 너무 이전 소수 문제들 때문에 소수 배열을 써야 풀 수 있다고 생각을 좁게 해버렸다.

  • 최근 제출 기록들 중에서 걸린 시간이 제일 길어서 뻘줌하다.

• 문제를 더 간단하게 생각하자.

  • 자연수 n을 i로 나눌 때 몫이 1보다 크고, 나머지가 0이 아닐 때 까지 i로 나눈다
  • 더 이상 i로 못 나누면 i+1로 과정을 반복한다.

• 만약 소인수 찾는 코드를 썼다면, 이 코드처럼 884ms라는 시간이 걸린다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		if (n == 1) { return; }		
		
		// making custom Eratosthenes set(from wikipedia)
		List<Boolean> eratos = new ArrayList<>();
		eratos.add(0, false); eratos.add(1, false);
		for (int i = 2; i <= n; i++) {
			eratos.add(i, true);
		}
		for (int i = 2; i*i <= n; i++) {
			if (eratos.get(i)) {
				for (int j = i*i; j <= n; j+=i) {
					eratos.set(j, false);
				}
			}
		}
		
		int divide = n;
		for(int i = 2; i <= n; i++) {
			if(eratos.get(i)) {
				while (divide%i ==0) {
					System.out.println(i);
					divide /= i;
				}
			}
		}	
		br.close();
	}
}

• 하지만 이 코드는 무려 160ms밖에 안 걸렸다.

import java.io.*;

public class Main {
// 내가 왜 굳이 이전에 써먹던 소인수분해 배열을 가져다가 써서 시간이..
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		if (n == 1) { return; }	
		for(int i = 2; i <= n; i++) {
			while (n%i ==0) {
				System.out.println(i);
				n /= i;
			}
		}	
		br.close();
	}
}